//31.下一个排列
//https://leetcode.cn/problems/next-permutation/
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return;
        int i = n - 2, j = n - 1, k = n - 1;

        //先找到第一个降序的区间
        while (i >= 0 && nums[i] >= nums[j]) --i, --j;
        //如果i<0 表示该序列全部为降序序列 此时只需要返回最小序列即可
        if (i >= 0)
        {
            //否则在[j,n-1]区间中找一个比 找一个比i小的数交换
            //分为[0,i] [j,n-1]两个区间 前面为小区间 后面为大区间 每次从大区间选一个最小的数加入小区间 小区间选一个大数到大区间
            //这样小区间最大的数和大区间最小的数差值最小 其组合也是唯一
            while (nums[i] >= nums[k]) --k;
            swap(nums[i], nums[k]);
        }

        //将[j,n-1]的区间置为升序
        for (i = j, j = n - 1; i < j; ++i, --j) swap(nums[i], nums[j]);

        //next_permutation(nums.begin(),nums.end()); //官方接口
    }
};